package com.mlh.dp.回文;

/**
 * @author 缪林辉
 * @date 2024/9/12 11:21
 * @DESCRIPTION
 */
// 给你一个字符串 s，找到 s 中最长的回文子串并返回
// 输入：s = "babad"
// 输出："bab"
// 解释："aba" 同样是符合题意的答案。
public class 最长回文子串 {
    public String method1(String s) {
        if (s.length() < 2) {
            return s;
        }
        int len = s.length();
        // dp数组的含义是 下标i-j组成的字符串是否为回文
        boolean[][] dp = new boolean[len][len];
        // 初始化
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        //这里设置成这个默认值是为了方便字符串中最长回文子串为单个字符时输出第一个字符为答案
        int maxLen = 1;
        int startIndex = 0;
        // 这里以子串长度为遍历条件
        for (int L = 2; L <= len; L++) {
            // i为子串的左边界，右边界通过L推出
            for (int i = 0; i < len; i++) {
                int right = i + L - 1;
                //右边界超出则退出本次循环
                if (right >= len) {
                    break;
                }
                //判断首尾两个字符是否相同
                if (s.charAt(i) == s.charAt(right)) {
                    if (L == 2) {
                        dp[i][right] = true;
                    } else {
                        dp[i][right] = dp[i + 1][right - 1];
                    }
                }
                //更新长度和startIndex
                if (dp[i][right] == true) {
                    if (maxLen < L) {
                        maxLen = L;
                        startIndex = i;
                    }
                }
            }
        }
        return s.substring(startIndex, startIndex + maxLen);
    }
}
